package main

import "fmt"

// 归并排序的递归实现
// https://segmentfault.com/a/1190000022288880
func mergeSort(nums []int) []int  {
	n := len(nums)
	if n < 2 {    // 递归退出条件
		return nums
	}
	mid := n / 2
	lNums := nums[:mid]
	l := len(lNums)
	if l >= 2 {
		lNums = mergeSort(lNums)
	}

	rNums := nums[mid:]
	r := len(rNums)
	if r >= 2 {
		rNums = mergeSort(rNums)
	}

	/*
	合并
	 */
	temp := make([]int, 0)
	i, j := 0, 0
	for i < l && j < r {
		if lNums[i] < rNums[j] {
			temp = append(temp, lNums[i])
			i ++
		}else {
			temp = append(temp, rNums[j])
			j ++
		}
	}
	if i < l {   // 少的那一边已经合并完成了
		temp = append(temp, lNums[i:]...)
	}
	if j < r {
		temp = append(temp, rNums[j:]...)
	}
	return temp
}


func main() {
	result := mergeSort([]int{3,1,0,-9,10, 900})
	fmt.Println(result)
}
